//
// Created by 10377 on 2023/12/2.
//
#include "BinaryTree.h"
#include <algorithm>
#include <stack>
#include <queue>
using std::stack;
using std::queue;

/**
 * 根据vector数组创建二叉树
 * @param input
 */
void BinaryTree::CreateTree(vector<int> input) {
    this->root = CreateTree(input, 0);
}

TreeNode *BinaryTree::CreateTree(vector<int> input, int n){

    TreeNode *temp = nullptr;

    if(n < input.size() && input[n] != -1){
        temp = new TreeNode(input[n]); //注意，使用指针先new出来才会有效果
        if(2 * n + 1 < input.size() &&  input[2 * n + 1] != -1){
            temp->left = CreateTree(input, 2 * n + 1);
        }
        if(2 * n + 2 < input.size() && input[2 * n + 2]  != -1){
            temp->right = CreateTree(input, 2 * n + 2);
        }
    }
    return temp;
}


void BinaryTree::DeleteTree(TreeNode *root){
    if(root->left != nullptr)
        DeleteTree(root->left);

    if(root->right != nullptr)
        DeleteTree(root->right);

    delete root;
}


/*-------------------------------------- 二叉树的前序遍历 --------------------------------------*/
/**
 * 二叉树的前序递归遍历公有方法
 * @param root
 * @return
 */
vector<int> BinaryTree::preorderRecTraversal() {
    return preorderRecTraversal(this->root);
}

/**
 * 二叉树的前序迭代遍历公有方法
 * @param root
 * @return
 */
vector<int> BinaryTree::preorderIteTraversal() {
    return preorderIteTraversal(this->root);
}

/**
 * 二叉树的前序递归遍历
 * @param root
 * @return
 */
vector<int> BinaryTree::preorderRecTraversal(TreeNode *root) {
    if(root == nullptr)
        return {};
    static vector<int> result;
    result.push_back(root->val);
    if (root->left != nullptr)
        preorderRecTraversal(root->left);
    if (root->right != nullptr)
        preorderRecTraversal(root->right);
    return result;
}

/**
 * 二叉树的前序迭代遍历
 * @param root
 * @return vector<int>
 *
 * 前序的迭代遍历需要创建一个栈，然后先放进去根节点
 * 然后循环判断栈是否为空，不为空就先出栈
 * 然后将右结点入栈，再将左结点入栈
 */
vector<int> BinaryTree::preorderIteTraversal(TreeNode *root) {
    if(root == nullptr)
        return {};

    stack<TreeNode *> tnStack;
    vector<int> res;
    tnStack.push(root);

    while (!tnStack.empty()) {
        TreeNode *temp = tnStack.top();
        tnStack.pop();
        res.push_back(temp->val);

        if (temp->right)
            tnStack.push(temp->right);
        if (temp->left)
            tnStack.push(temp->left);
    }
    return res;
}


/*-------------------------------------- 二叉树的中序遍历 --------------------------------------*/
/**
 * 二叉树的中序递归遍历公有方法
 * @param root
 * @return
 */
vector<int> BinaryTree::inorderRecTraversal() {
    return inorderRecTraversal(this->root);
}

/**
 * 二叉树的中序迭代遍历公有方法
 * @param root
 * @return
 */
vector<int> BinaryTree::inorderIteTraversal() {
    return inorderIteTraversal(this->root);
}

/**
 * 二叉树的中序递归遍历
 * @param root
 * @return
 */
vector<int> BinaryTree::inorderRecTraversal(TreeNode *root) {
    if(root == nullptr)
        return {};
    static vector<int> result;

    if (root->left != nullptr)
        inorderRecTraversal(root->left);
    result.push_back(root->val);
    if (root->right != nullptr)
        inorderRecTraversal(root->right);
    return result;
}

/**
 * 二叉树的中序迭代遍历
 * @param root
 * @return
 *
 * 当前结点或者栈非空的时候：
 * 1.一直往左走
 * 2.若不能往左走了，那就出栈顶放入结果数据
 *   然后往右走
 */
vector<int> BinaryTree::inorderIteTraversal(TreeNode *root) {
    if(root == nullptr)
        return {};
    vector<int> res;
    stack<TreeNode*> tnStack;
    TreeNode* cur = root;

    while(cur != nullptr || !tnStack.empty()){
        if(cur != nullptr){
            tnStack.push(cur);
            cur = cur->left;
        }
        else{
            cur = tnStack.top();
            res.push_back(cur->val);
            tnStack.pop();
            cur = cur->right;
        }
    }
    return res;
}

/*-------------------------------------- 二叉树的后序遍历 --------------------------------------*/
/**
 * 二叉树的后序递归遍历公有方法 左右根
 * @param root
 * @return
 */
vector<int> BinaryTree::postorderRecTraversal() {
    return postorderRecTraversal(this->root);
}

/**
 * 二叉树的后序迭代遍历公有方法 左右根
 * @param root
 * @return
 */
vector<int> BinaryTree::postorderIteTraversal() {
    return postorderIteTraversal(this->root);
}

/**
 * 二叉树的后序递归遍历
 * @param root
 * @return
 */
vector<int> BinaryTree::postorderRecTraversal(TreeNode *root) {
    if(root == nullptr)
        return {};
    static vector<int> result;

    if (root->left != nullptr)
        postorderRecTraversal(root->left);
    if (root->right != nullptr)
        postorderRecTraversal(root->right);
    result.push_back(root->val);
    return result;
}

/**
 * 二叉树的后序迭代遍历
 * @param root
 * @return
 */
vector<int> BinaryTree::postorderIteTraversal(TreeNode *root) {
    if(root == nullptr)
        return {};

    stack<TreeNode *> tnStack;
    vector<int> res;
    tnStack.push(root);    //根

    while (!tnStack.empty()) {
        TreeNode *temp = tnStack.top();
        tnStack.pop();
        res.push_back(temp->val);

        if (temp->left)      //左
            tnStack.push(temp->left);
        if (temp->right)     //右
            tnStack.push(temp->right);
    }
    reverse(res.begin(), res.end());
    return res;
}


vector<vector<int>> BinaryTree::levelOrderTraversal(){
    return levelOrderTraversal(this->root);
}


/**
 * 二叉树层序遍历
 * @param root
 * @return
 * 1.取队列的长度；
 * 2.循环遍历，在遍历过程中将下一次入队。
 * 队列长度size是单独取出来的，不会遍历到下一层
 */
vector<vector<int>> BinaryTree::levelOrderTraversal(TreeNode* root){
    if(root == nullptr)
        return {};

    queue<TreeNode*> tnQueue;
    tnQueue.push(root);
    vector<vector<int>> res;

    while(!tnQueue.empty()){
       vector<int> levelVec;
       int size = tnQueue.size();
       for(int i = 0; i <  size; i++){
           TreeNode *temp = tnQueue.front();
           levelVec.push_back(temp->val);
           if(temp->left)  tnQueue.push(temp->left);
           if(temp->right) tnQueue.push(temp->right);
           tnQueue.pop();
       }
       res.push_back(levelVec);
    }
    return res;
}


/**
 * 横向绘制二叉树
 */
void BinaryTree::drawTree() {
    drawTree(this->root, 0);
}

void BinaryTree::drawTree(TreeNode *root, int depth) {
    if(root->right != nullptr)
        drawTree(root->right, depth + 1);
    for(int i = 0; i < depth; ++i){
        cout<<"     ";
    }
    cout << root->val<<endl;
    if(root->left != nullptr)
        drawTree(root->left, depth + 1);
}

/**
 * 镜面翻转二叉树
 */
void BinaryTree::invertTree() {
    invertTree(this->root);
}

void BinaryTree::invertTree(TreeNode *root) {
    if(root == nullptr)
        return;
    invertTree(root->left);
    invertTree(root->right);
    TreeNode * temp = root->left;
    root->left = root->right;
    root->right = temp;
}

/**
 * 获取二叉树的高度
 * @param root 根结点
 * @param n 当前的高度
 * @return
 */
int BinaryTree::getHeight(TreeNode *root, int n) {
    int left = n, right = n;
    if(root->left)
        left = getHeight(root->left, n + 1);
    if(root->right)
        right = getHeight(root->right, n + 1);
    return left > right ? left : right;
}

bool BinaryTree::isBalanced() {
    return isBalanced(this->root);
}


bool BinaryTree::isBalanced(TreeNode *root) {
    if(root == nullptr)  return true;
    int left = 0, right = 0;
    if(root->left)  left = getHeight(root->left, 1);
    if(root->right) right = getHeight(root->right, 1);
    if(abs(left - right) > 1) return false;
    if(!isBalanced(root->left) || !isBalanced(root->right)) return false;
    return true;
}

void BinaryTree::getPath(TreeNode *root, string curPath) {
    if(root->left == nullptr &&  root->right == nullptr)
        res.push_back(curPath + "->" + to_string(root->val));
    if(root->left)
        getPath(root->left, curPath + "->" +to_string(root->val));
    if(root->right)
        getPath(root->right, curPath + "->" +  to_string(root->val));
}

vector<string> BinaryTree::binaryTreePaths(){
  return  binaryTreePaths(root);
}

vector<string> BinaryTree::binaryTreePaths(TreeNode* root) {
    if(root == nullptr)
        return {};
    if(root->left == nullptr && root->right == nullptr)
        res.push_back(to_string(root->val));
    else{
        string str = to_string(root->val);
        if(root->left)  getPath(root->left, str);
        if(root->right) getPath(root->right, str);
    }
    return res;
}


/**
 * 横向绘制二叉树
 * @param root 根节点
 * @param depth 写 0
 */
void drawTreePublic(TreeNode* root, int depth){

    if(root->right != nullptr)
        drawTreePublic(root->right, depth + 1);
    for(int i = 0; i < depth; ++i){
        cout<<"     ";
    }
    cout << root->val<<endl;
    if(root->left != nullptr)
        drawTreePublic(root->left, depth + 1);

}


/**
 * 根据中序遍历和后序遍历创建二叉树
 * @param inorder
 * @param postorder
 * @return
 */
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
    TreeNode* root = nullptr;
    int size = postorder.size();
    if(size == 0)
        return root;
    if(size == 1){
        root = new TreeNode();
        root->val = postorder[0];
        return root;
    }

    int temp = postorder[postorder.size() - 1];
    int indexInorder = 0;
    for(;;++indexInorder){
        if(inorder[indexInorder] == temp)
            break;
    }
    root = new TreeNode();
    root->val = inorder[indexInorder];

    if(indexInorder > 0){
        vector<int> inorderLeft, postorderLeft;
        inorderLeft.assign(inorder.begin(), inorder.begin() + indexInorder);
        postorderLeft.assign(postorder.begin() , postorder.begin() + indexInorder);
        root->left = buildTree(inorderLeft, postorderLeft);
    }

    if(indexInorder < size - 1){
        vector<int> inorderRight, postorderRight;
        inorderRight.assign(inorder.begin() + indexInorder + 1, inorder.end());
        postorderRight.assign(postorder.begin() + indexInorder, postorder.end() - 1);
        root->right = buildTree(inorderRight,postorderRight);
    }
    return root;
}



/**
 * 最大二叉树
 * @param nums
 * @return
 */
TreeNode* constructMaximumBinaryTree(vector<int>& nums){

    int size = nums.size();
    if(size == 0)
        return nullptr;
    TreeNode *root = new TreeNode();
    if(size == 1){
        root->val = nums[0];
        return root;
    }

    int index = 0;
    for(int i = 0; i < size;++i) {
        if (nums[index] < nums[i])
            index = i;
    }
    root->val = nums[index];
    //[3, 2, 1, 6, 0, 5]
    vector<int> left, right;
    if(index > 0){
        left.assign(nums.begin(), nums.begin() + index);
        root->left = constructMaximumBinaryTree(left);
    }
    if(index < size - 1){
        right.assign(nums.begin()+ index + 1, nums.end() );
        root->right = constructMaximumBinaryTree(right);
    }
    return root;
}


/**
 * 合并二叉树
 * @param root1
 * @param root2
 * @return
 */
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
    if(root1 == nullptr && root2 == nullptr)
        return nullptr;
    if(root1 == nullptr && root2 != nullptr){
        root1 = new TreeNode();
        root1->val = root2->val;
    }
    else if(root1 != nullptr && root2 != nullptr)){
        root1->val += root2->val;
    }
    if(root2->left != nullptr)
        root1->left = mergeTrees(root1->left, root2->left);
    if(root2->right != nullptr)
        root1->right = mergeTrees(root1->right, root2->right);
    return root1;
}